{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #连续数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMaxLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #连续数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二进制数组 <code>nums</code> , 找到含有相同数量的 <code>0</code> 和 <code>1</code> 的最长连续子数组，并返回该子数组的长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [0,1]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>说明:</strong> [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [0,1,0]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>说明:</strong> [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums[i]</code> 不是 <code>0</code> 就是 <code>1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 525&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/contiguous-array/\">https://leetcode-cn.com/problems/contiguous-array/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [A1NYOS](https://leetcode.cn/problems/A1NYOS/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [A1NYOS](https://leetcode.cn/problems/A1NYOS/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1]', '[0,1,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        maxLength = 0\n",
    "        counter = 0\n",
    "        map = {0: -1}\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            num = nums[i]\n",
    "            if num == 1:\n",
    "                counter += 1\n",
    "            else:\n",
    "                counter -= 1\n",
    "            if counter in map:\n",
    "                prevIndex = map[counter]\n",
    "                maxLength = max(maxLength, i - prevIndex)\n",
    "            else:\n",
    "                map[counter] = i\n",
    "        return maxLength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        # 数组、哈希表、前缀和\n",
    "        # 0和1的数量相同，等价于1的数量减去0的数量等于0\n",
    "        # 我们可将数组中0视作-1，则原问题转换为求最长的连续子数组，其元素和为0\n",
    "        maxlength = 0\n",
    "        presum = 0\n",
    "        # 定义哈希表，键值对为 前缀和：首次出现该前缀和时的索引\n",
    "        # 规定空的前缀和的下标为-1，空前缀和的元素和为0，因此在遍历前在哈希表中存入键值对(0, -1)\n",
    "        dic = {0: -1}\n",
    "        n = len(nums)\n",
    "        for k, v in enumerate(nums):\n",
    "            # 遍历数组，遇到1时，presum加1，遇到0时，presum减1\n",
    "            if v == 1:\n",
    "                presum += 1\n",
    "            else:\n",
    "                presum -= 1\n",
    "            # 关键：如果当前前缀和出现在字典中，说明该前缀和在前面出现过，不断添加n个元素后，前缀和仍为\n",
    "            # 当前前缀和的值，说明中间的这n个元素和为0。\n",
    "            if presum in dic:\n",
    "                # 此时更新最终结果，用当前下标减去第一次出现的下标。即为当前最长连续子数组\n",
    "                # 此时无需更新字典中的下标位置，是因为如果后面再次出现相同的前缀和，仍说明\n",
    "                # 这中间的m个元素和为0。\n",
    "                firstindex = dic[presum]\n",
    "                maxlength = max(maxlength, k - firstindex)\n",
    "            else:\n",
    "                # 若没出现则将当前第一次出现的前缀和添加到字典中。\n",
    "                dic[presum] = k\n",
    "        return maxlength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        presum = {0:-1}\n",
    "        s = 0\n",
    "        maxlen = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 0:\n",
    "                s -= 1\n",
    "            else:\n",
    "                s += 1\n",
    "            if s in presum:\n",
    "                presum[s] = min(presum[s],i)\n",
    "            else:\n",
    "                presum[s] = i\n",
    "            if  s-0 in presum:\n",
    "                left = presum[s-0]\n",
    "                maxlen = max(maxlen,i - presum[s-0])\n",
    "                \n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        maxlength, presum = 0, 0\n",
    "        dic = {0: -1}\n",
    "        for k, v in enumerate(nums):\n",
    "            if v == 1:\n",
    "                presum += 1\n",
    "            else:\n",
    "                presum -= 1\n",
    "            if presum in dic:\n",
    "                firstindex = dic[presum]\n",
    "                maxlength = max(maxlength, k - firstindex)\n",
    "            else:\n",
    "                dic[presum] = k\n",
    "        return maxlength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        prefix_sum = 0\n",
    "        sum_mapping = {0:-1}\n",
    "        ans = 0\n",
    "        for idx,num in enumerate(nums):\n",
    "            if num==0:\n",
    "                prefix_sum -=1\n",
    "            else:\n",
    "                prefix_sum += 1\n",
    "            if prefix_sum not in sum_mapping:\n",
    "                sum_mapping[prefix_sum] = idx\n",
    "            else:\n",
    "                ans = max(ans,idx-sum_mapping[prefix_sum])\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        mp = {0: -1}\n",
    "        ans = 0\n",
    "        s = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            s += 1 if x else -1\n",
    "            if s in mp:\n",
    "                ans = max(ans, i-mp[s])\n",
    "            else:\n",
    "                mp[s] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        hashmap={0:-1}\n",
    "        c=ans=0\n",
    "        for i,num in enumerate(nums):\n",
    "            if num==1:\n",
    "                c+=1\n",
    "            else:\n",
    "                c-=1\n",
    "            if c in hashmap:\n",
    "                ans=max(ans,i-hashmap[c])\n",
    "            else:\n",
    "                hashmap[c]=i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        pre_dict = {}\n",
    "        res = 0\n",
    "        pre = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            curr = num if num == 1 else -1\n",
    "            pre += curr\n",
    "            if pre == 0:\n",
    "                res = i + 1\n",
    "            if pre not in pre_dict:\n",
    "                pre_dict[pre] = i\n",
    "            else:\n",
    "                res = max(res, i - pre_dict[pre])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        pre = [0]\n",
    "        cache = {0:0}\n",
    "        res = 0\n",
    "        for i in nums:\n",
    "            if i == 0 :\n",
    "                pre.append(pre[-1]-1)\n",
    "            else:\n",
    "                pre.append(pre[-1]+i)\n",
    "            \n",
    "            if pre[-1] in cache:\n",
    "                r = len(pre)-1\n",
    "                l = cache[pre[-1]]\n",
    "                res = max(res, r-l)\n",
    "            if pre[-1] not in cache:\n",
    "                cache[pre[-1]] = len(pre)-1\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        hs = {0:-1}\n",
    "        res, sm = 0, 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 0: sm -= 1\n",
    "            else: sm += 1\n",
    "            if sm in hs: res = max(res, i-hs[sm])\n",
    "            else: hs[sm] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        pre = [0]\n",
    "        cache = {0:0}\n",
    "        res = 0\n",
    "        for i in nums:\n",
    "            if i == 0 :\n",
    "                pre.append(pre[-1]-1)\n",
    "            else:\n",
    "                pre.append(pre[-1]+i)\n",
    "            \n",
    "            if pre[-1] in cache:\n",
    "                r = len(pre)-1\n",
    "                l = cache[pre[-1]]\n",
    "                res = max(res, r-l)\n",
    "            if pre[-1] not in cache:\n",
    "                cache[pre[-1]] = len(pre)-1\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]):\n",
    "        dic={}\n",
    "        total=ans=0\n",
    "        dic[0]=-1\n",
    "        for i in range(len(nums)):\n",
    "            total+=(1 if nums[i]==1 else -1)\n",
    "            if total not in dic:\n",
    "                dic[total]=i\n",
    "            else:\n",
    "                ans=max(ans,i-dic[total])\n",
    "\n",
    "\n",
    "\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        cur_dict = {0:0, 1:0}\n",
    "        prefixDiffLeftIndexDict = {0:-1}  # 记录所有diff的最左边界\n",
    "        longest_len = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            cur_dict[0 if nums[i] == 0 else 1] += 1\n",
    "            cur_diff = cur_dict[1] - cur_dict[0]\n",
    "\n",
    "            if cur_diff in prefixDiffLeftIndexDict:\n",
    "                longest_len = max(longest_len, i-prefixDiffLeftIndexDict[cur_diff])\n",
    "            else:\n",
    "                prefixDiffLeftIndexDict[cur_diff] = i\n",
    "        return longest_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        hashmap = dict()\n",
    "        preSum = 0\n",
    "        oneSum = 0\n",
    "        for i in range(0, len(nums)):\n",
    "            oneSum = preSum + nums[i]\n",
    "            search = i - oneSum * 2 + 1\n",
    "            new_key = i - oneSum * 2 + nums[i] * 2\n",
    "            if search in hashmap.keys():\n",
    "                ans = max(ans, i - hashmap[search] + 1)\n",
    "            if new_key not in hashmap.keys():\n",
    "                hashmap[new_key] = i\n",
    "            preSum = oneSum\n",
    "\n",
    "        return ans\n",
    "        #\n",
    "        # i - pre + 1 == (preSum[i] - preSum[pre]) * 2\n",
    "        # 即\n",
    "        # i - preSum[i] * 2 + 1 == pre - preSum[pre] * 2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        max_len = 0\n",
    "        s = 0\n",
    "        c = {0:-1}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 0:\n",
    "                s -= 1\n",
    "            else:\n",
    "                s += 1\n",
    "            if s in c:\n",
    "                index = c[s]\n",
    "                max_len = max(max_len, i-index)\n",
    "            else:\n",
    "                c[s] = i\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 把0变成-1，找到和为0的最长子数组\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        temp = []\n",
    "        for v in nums:\n",
    "            if v == 0:\n",
    "                temp.append(-1)\n",
    "            else:\n",
    "                temp.append(1)\n",
    "\n",
    "        dic = {}\n",
    "        total = 0\n",
    "        res = 0\n",
    "        for i in range(len(temp)):\n",
    "            total += temp[i]\n",
    "            if total == 0:\n",
    "                res = max(res, i+1)\n",
    "            if total in dic:\n",
    "                res = max(res, i-dic[total])\n",
    "            \n",
    "            if total not in dic:\n",
    "                dic[total] = i\n",
    "  \n",
    "\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        d = {}\n",
    "        rs = 0\n",
    "        tmp_sum = 0\n",
    "        for idx, num in enumerate(nums):  # 0转为-1，这样和为0的时候二者数量是一样的，0多的时候取前一个相同数量0的位置到当前位置即可\n",
    "            if num==0:\n",
    "                tmp_sum += -1\n",
    "            else:\n",
    "                tmp_sum += 1\n",
    "            if tmp_sum in d:\n",
    "                rs = max(rs, idx-d[tmp_sum])\n",
    "            else:\n",
    "                if tmp_sum==0:  # 第一次和为0即第一次数量相等且未记录时，说明从开头到当前数量一样，故0的前一个下标取-1\n",
    "                    rs = max(rs, idx+1)\n",
    "                    d[0] = -1\n",
    "                else:\n",
    "                    d[tmp_sum] = idx\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        diffnum = defaultdict(int)\n",
    "        diffnum[0] = -1\n",
    "        diff = 0\n",
    "        n = len(nums)\n",
    "        maxlen = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == 1:\n",
    "                diff += 1\n",
    "            else:\n",
    "                diff -= 1\n",
    "            \n",
    "            if diff in diffnum:\n",
    "                maxlen = max(maxlen, i-diffnum[diff])\n",
    "            else:\n",
    "                diffnum[diff] = i\n",
    "        \n",
    "        return maxlen\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        preSum = []\n",
    "        res = 0\n",
    "        mapLeft = dict()\n",
    "        mapLeft[0] = -1\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 0:\n",
    "                nums[i] = -1\n",
    "            if i == 0:\n",
    "                preSum.append(nums[i])\n",
    "            else:\n",
    "                preSum.append(preSum[i - 1] + nums[i])\n",
    "            if preSum[i] in mapLeft:\n",
    "                res = max(res, i - mapLeft[preSum[i]])\n",
    "            if preSum[i] not in mapLeft:\n",
    "                mapLeft[preSum[i]] = i\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        nums = [1 if i==1 else -1  for i in nums]\n",
    "        presum = {0:-1}\n",
    "        p,m = 0,0\n",
    "        for i,n in enumerate(nums):\n",
    "            p += n \n",
    "            if p not in presum:\n",
    "                presum[p] = i\n",
    "            else:\n",
    "                m = max(m,i-presum[p])\n",
    "        return m\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        dicts = {}\n",
    "        count = 0\n",
    "        max_ = 0\n",
    "        # 0 就等于 -1\n",
    "        dicts[0] = -1\n",
    "        for i, v in enumerate(nums[:]):\n",
    "            if v == 0:\n",
    "                v = -1\n",
    "            count += v\n",
    "            if count in dicts:\n",
    "                max_ = max(i - dicts[count], max_)\n",
    "            else:\n",
    "                dicts[count] = i\n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        dic = {}\n",
    "        dic[0] = 0\n",
    "\n",
    "        pre_sum = [0] * (len(nums)+1)\n",
    "        for i in range(1, len(nums)+1):\n",
    "            pre_sum[i] = pre_sum[i-1] + (-1 if nums[i-1]==0 else 1)\n",
    "\n",
    "        for i in range(1, len(nums)+1):\n",
    "            if pre_sum[i] in dic:\n",
    "                res = max(res, i - dic.get(pre_sum[i]))\n",
    "            else:\n",
    "                dic[pre_sum[i]] = i\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                nums[i] = -1\n",
    "        newnums = [0] * n\n",
    "        newnums[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            newnums[i] = newnums[i-1] + nums[i]\n",
    "        ha = {0: -1}\n",
    "        maxlen = 0\n",
    "        for i in range(n):\n",
    "            if newnums[i] in ha:\n",
    "                maxlen = max(i-ha[newnums[i]], maxlen)\n",
    "            else:\n",
    "                ha[newnums[i]] = i\n",
    "        # print(newnums)\n",
    "        return maxlen\n",
    "        \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        frontSum = [0]\n",
    "        for i in range(n):\n",
    "            if nums[i] == 1:\n",
    "                frontSum.append(frontSum[i] + 1)\n",
    "            else:\n",
    "                frontSum.append(frontSum[i] - 1)\n",
    "        hashSet = dict()\n",
    "        res = 0\n",
    "        for i in range(1, n+1):\n",
    "            if frontSum[i] == 0:\n",
    "                res = max(res, i)\n",
    "            elif frontSum[i] in hashSet:\n",
    "                res = max(res, i - hashSet[frontSum[i]])\n",
    "            else:\n",
    "                hashSet[frontSum[i]] = i\n",
    "        print(hashSet)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        mp = {0:0}\n",
    "        pre = [0]*(n+1)\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            v = 1 if nums[i-1]>0 else -1\n",
    "            pre[i] = pre[i-1] + v\n",
    "\n",
    "            t = pre[i]\n",
    "            if t in mp:\n",
    "                ans = max(ans, i-mp[t])\n",
    "            else:\n",
    "                mp[t] = i \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        #把0置为-1\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i]==0:\n",
    "                nums[i]=-1\n",
    "        #把问题转化为和为0的最长连续子数组长度\n",
    "        #很典吧\n",
    "        #前缀和+哈希表\n",
    "        x=dict()\n",
    "        arr=list(accumulate(nums,initial=0))\n",
    "        ans=0\n",
    "        n=len(arr)\n",
    "        for i in range(n):\n",
    "            if arr[i] in x:\n",
    "                ans=max(ans,i-x[arr[i]])\n",
    "            else:\n",
    "                x[arr[i]]=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                nums[i] = -1\n",
    "        count = [0]\n",
    "        count_dic = {0:-1}\n",
    "        for j in range(n):\n",
    "            \n",
    "            if count[-1]+nums[j] not in count_dic:\n",
    "                count_dic[count[-1]+nums[j]] = j\n",
    "            else:\n",
    "                ans = max(j-count_dic[count[-1]+nums[j]],ans)\n",
    "            count.append(count[-1]+nums[j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        # 边界条件\n",
    "        if len(nums) < 2: return 0\n",
    "\n",
    "        # 累积和\n",
    "        res = 0\n",
    "        sumMap = collections.defaultdict(list)\n",
    "        sumMap[0] = [-1]\n",
    "        acc1, acc0 = 0, 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "\n",
    "            if nums[i] == 0:\n",
    "                acc0 += 1\n",
    "            else:\n",
    "                acc1 += 1\n",
    "            \n",
    "            cur_diff = acc0 - acc1\n",
    "            sumMap[cur_diff].append(i)\n",
    "\n",
    "            # 判断是否存在相同的\n",
    "            if cur_diff in sumMap:\n",
    "                res = max(res, i - sumMap[cur_diff][0])\n",
    "            \n",
    "\n",
    "        # print(sum0)\n",
    "        # print(sum1)\n",
    "\n",
    "        # 遍历\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "    def findMaxLength2(self, nums: List[int]) -> int:\n",
    "\n",
    "        # 边界条件\n",
    "        if len(nums) < 2: return 0\n",
    "\n",
    "        # 累积和\n",
    "        sum1, sum0 = [0]*(len(nums) + 1), [0]*(len(nums) + 1)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 0:\n",
    "                sum0[i+1] = sum0[i]+1\n",
    "                sum1[i+1] = sum1[i]\n",
    "\n",
    "            else:\n",
    "                sum0[i+1] = sum0[i]\n",
    "                sum1[i+1] = sum1[i] + 1\n",
    "\n",
    "        # print(sum0)\n",
    "        # print(sum1)\n",
    "\n",
    "        # 遍历\n",
    "        res = 0\n",
    "        for i in range(1, len(sum0)):\n",
    "            for j in range(0, i):\n",
    "\n",
    "                if sum0[i] - sum0[j] == sum1[i] - sum1[j]:\n",
    "                    res = max(res, i - j)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        pre = 0\n",
    "        mp = dict()\n",
    "        mp_set = set()\n",
    "        mp[0] = -1\n",
    "        mp_set.add(0)\n",
    "        ans = -1\n",
    "        for idx, x in enumerate(nums):\n",
    "            if x:\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre -= 1\n",
    "            if pre in mp_set:\n",
    "                if ans < idx - mp[pre]:\n",
    "                    ans = idx - mp[pre]\n",
    "            else:\n",
    "                mp[pre] = idx\n",
    "                mp_set.add(pre)\n",
    "        if ans < 0:\n",
    "            return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = nums[i] - 0.5\n",
    "\n",
    "        sums = 0\n",
    "        memo = {0:-1}\n",
    "        max_len = 0\n",
    "        for i in range(len(nums)):\n",
    "            sums += nums[i]\n",
    "            if sums in memo:\n",
    "                max_len = max(max_len, i-memo[sums])\n",
    "            else:\n",
    "                memo[sums] = i\n",
    "\n",
    "        return max_len\n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n=nums.copy()\n",
    "        size=len(n)\n",
    "        for i in range(0,size): #把0全替换成-1\n",
    "            if n[i]==0:\n",
    "                n[i]=-1\n",
    "\n",
    "        preSum=[0]*(size+1) #前缀和，preSum[i]表示前i个元素的和，实际上由于我们进行了替换，因此我们可以得到前i个元素中1比0多了preSum[i]个\n",
    "        preSum[0]=0\n",
    "        for i in range(0,size):\n",
    "            preSum[i+1]=preSum[i]+n[i] #前i+1个元素的和等于前i个元素的和加上数组n的第n+1个元素\n",
    "        \n",
    "        MAX=0\n",
    "        dict={0:0} #key表示前缀和，value表示该key最早出现在preSum[value]中\n",
    "        for i in range(1,size+1):\n",
    "            if preSum[i] in dict: \n",
    "                MAX=max(MAX,i-dict[preSum[i]]) #两前缀和之差为0，若另一前缀和在dict中，说明此时有一个相同数量的最长连续子数组，尝试将其长度与MAX进行比较\n",
    "            else:\n",
    "                dict[preSum[i]]=i #该前缀和不在dict中，则加入，且value设为i\n",
    "        return MAX\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 2 and sum(nums) == 1: return 2\n",
    "        dic = defaultdict(list)\n",
    "        dic[0].append(0)\n",
    "        tot = 0\n",
    "        for i in range(1, len(nums)+1):\n",
    "            if nums[i-1] == 0:\n",
    "                tot += -1\n",
    "            else:\n",
    "                tot += 1\n",
    "            dic[tot].append(i)\n",
    "        \n",
    "        res = 0\n",
    "        # print(dic)\n",
    "        for k, v in dic.items():\n",
    "            if len(v)>1:\n",
    "                res = max(res, v[-1]-v[0])\n",
    "      \n",
    "         \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = nums[i] - 0.5\n",
    "\n",
    "        sums = 0\n",
    "        memo = {0:-1}\n",
    "        max_len = 0\n",
    "        for i in range(len(nums)):\n",
    "            sums += nums[i]\n",
    "            if sums in memo:\n",
    "                memo[sums] = min(memo[sums], i)\n",
    "                max_len = max(max_len, i-memo[sums])\n",
    "            else:\n",
    "                memo[sums] = i\n",
    "\n",
    "        return max_len\n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        d = {}\n",
    "        nums = [2 * x - 1 for x in nums]\n",
    "        ans = 0\n",
    "        for i, x in enumerate([0] + list(accumulate(nums))):\n",
    "            if x not in d: d[x] = i\n",
    "            else: ans = max(ans, i-d[x])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "        nums = [x if x==1 else -1 for x in nums]\n",
    "\n",
    "        prefix_sum = []\n",
    "        tmp=0\n",
    "        for x in nums:\n",
    "            tmp +=x\n",
    "            prefix_sum.append(tmp)\n",
    "        print(nums)\n",
    "        print(prefix_sum)\n",
    "        prefix_dic = {0:-1}\n",
    "        res=0\n",
    "        for i,x in enumerate(prefix_sum):\n",
    "            if x in prefix_dic:\n",
    "                res = max(res,i-prefix_dic[x])\n",
    "            else:\n",
    "                prefix_dic[x]=i \n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        preSum = []\n",
    "        preSum.append(1 if nums[0] == 1 else -1)\n",
    "        for i in range(1,len(nums)):\n",
    "            add = 1 if nums[i] == 1 else -1\n",
    "            preSum.append(preSum[i-1] + add)\n",
    "\n",
    "        dict = {}\n",
    "        ans = 0\n",
    "        for i,x in enumerate(preSum):\n",
    "            if x == 0:\n",
    "                ans = max(i+1,ans)\n",
    "            elif x in dict:\n",
    "                ans = max(i-dict[x],ans)\n",
    "            if x not in dict:\n",
    "                dict[x] = i\n",
    "            else:\n",
    "                dict[x] = min(dict[x],i)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        elif n == 2:\n",
    "            return (nums[0] != nums[1])*2\n",
    "\n",
    "        res = 0\n",
    "        if nums[0] == 0:\n",
    "            nums[0] = -1\n",
    "        d = {}\n",
    "        d[nums[0]] = [0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == 0:\n",
    "                nums[i] = -1\n",
    "            nums[i] += nums[i-1]\n",
    "            if nums[i] == 0:\n",
    "                res = max(res, i+1)\n",
    "            d[nums[i]] = d.get(nums[i], []) + [i]\n",
    "            if i != d[nums[i]][0]:\n",
    "                res = max(res, i-d[nums[i]][0])\n",
    "        \n",
    "        return res\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        summary = 0\n",
    "        dic = defaultdict(list)\n",
    "        dic[0].append(-1)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 1:\n",
    "                summary = summary+1\n",
    "            else:\n",
    "                summary = summary-1\n",
    "            dic[summary].append(i)\n",
    "        ans = 0\n",
    "        for value in dic.values():\n",
    "            ans = max(ans,max(value)-min(value))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        n = len(nums)\n",
    "        mp = {0:0}\n",
    "        pre = [0]*(n+1)\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            v = 1 if nums[i-1]>0 else -1\n",
    "            pre[i] = pre[i-1]+ v\n",
    "\n",
    "            target_pre = pre[i] - 0\n",
    "            if target_pre in mp:\n",
    "                ans = max(ans, i-mp[target_pre])\n",
    "            else:\n",
    "                mp[target_pre] = i\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        sum_pre = {}\n",
    "        pre, ans = 0, 0\n",
    "        for i, num in enumerate(nums):\n",
    "            pre += num * 2 - 1\n",
    "            if pre in sum_pre.keys():\n",
    "                ans = max(ans, i - min(sum_pre[pre]))\n",
    "            if pre == 0:\n",
    "                ans = max(ans, i + 1)\n",
    "            if pre in sum_pre.keys():\n",
    "                sum_pre[pre].append(i)\n",
    "            else:\n",
    "                sum_pre[pre] = [i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        info, count, total = {0: [0]}, 0, 0\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = 1 if nums[i] == 1 else -1\n",
    "            total += nums[i]\n",
    "            if total not in info:\n",
    "                info[total] = []\n",
    "            info[total].append(i+1)\n",
    "        res = 0\n",
    "        for k in info:\n",
    "            if len(info[k]) >= 2:\n",
    "                tmp = info[k][-1] - info[k][0]\n",
    "                res = tmp if tmp > res else res\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                nums[i] = -1\n",
    "        pre = 0\n",
    "        dic = defaultdict(list)\n",
    "        dic[0].append(-1)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            pre += nums[i]\n",
    "            dic[pre].append(i)\n",
    "            res = max(res,i - dic[pre][0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        pre = 0\n",
    "        mp = {}\n",
    "        for i in range(len(nums)):\n",
    "            pre += nums[i] if nums[i] else -1\n",
    "            if pre not in mp:\n",
    "                mp[pre] =[i]\n",
    "            else:\n",
    "                mp[pre].append(i)\n",
    "        res = 0\n",
    "        for key in mp:\n",
    "            if key !=0:\n",
    "                res = max(res,mp[key][-1] - mp[key][0])\n",
    "            else:\n",
    "                res = max(res,mp[key][-1] + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        # if len(nums)==1:\n",
    "        #     return 0\n",
    "\n",
    "        # csum = [0]+[nums[0]]\n",
    "        # len_ = len(nums)\n",
    "        # for i, v in enumerate(nums):\n",
    "        #     if i >0:\n",
    "        #         csum.append(csum[-1]+v)\n",
    "\n",
    "        # max_ = 0\n",
    "        # for i, v in enumerate(nums):\n",
    "        #     j = i+1\n",
    "        #     while (j-i+1)%2 ==0 and j < len_:\n",
    "        #         val = csum[j+1]-csum[i]\n",
    "        #         if val == (j-i+1)/2:\n",
    "        #             max_ = max(max_, j-i+1)\n",
    "        #         j +=2 \n",
    "        #     if max_ > len_-i+1:\n",
    "        #         break \n",
    "        # return max_ \n",
    "        nums = [1 if i==1 else -1 for i in nums]\n",
    "        recmin = {}\n",
    "        recmax = {}\n",
    "        csum = [0]\n",
    "        for i, v in enumerate(nums):\n",
    "            csum.append(csum[-1]+v) \n",
    "        for i, v in enumerate(csum):\n",
    "            if v not in recmin:\n",
    "                recmax[v] = i \n",
    "                recmin[v] = i\n",
    "            else:\n",
    "                recmin[v] = min(i, recmin[v]) \n",
    "                recmax[v] = max(i, recmax[v])\n",
    "        max_ = 0\n",
    "        for i in recmin.keys():\n",
    "            max_ = max(max_, recmax[i]-recmin[i])\n",
    "\n",
    "        return max_ \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "                  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        sum_pre = {}\n",
    "        pre, ans = 0, 0\n",
    "        for i, num in enumerate(nums):\n",
    "            pre += num * 2 - 1\n",
    "            if pre in sum_pre.keys():\n",
    "                ans = max(ans, i - sum_pre[pre][0])\n",
    "            if pre == 0:\n",
    "                ans = max(ans, i + 1)\n",
    "            if pre in sum_pre.keys():\n",
    "                sum_pre[pre].append(i)\n",
    "            else:\n",
    "                sum_pre[pre] = [i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        prefix = {-1:0}\n",
    "        for i,j in enumerate(nums):\n",
    "            prefix[i] = prefix[i-1] + (1 if j==1 else -1)\n",
    "        tmp={}\n",
    "        ans=0\n",
    "        for i,j in prefix.items():\n",
    "            if j in tmp:\n",
    "                ans=max(ans,i-tmp[j])\n",
    "            else:\n",
    "                tmp[j]=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        count_0 = 0\n",
    "        count_1 = 0\n",
    "\n",
    "        pre = {0: -1}\n",
    "        post = {0: -1}\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                count_0 += 1\n",
    "            else:\n",
    "                count_1 += 1\n",
    "            \n",
    "            count_1_0 = count_1 - count_0\n",
    "\n",
    "            if count_1_0 not in pre:\n",
    "                pre[count_1_0] = i \n",
    "\n",
    "            post[count_1_0] = i \n",
    "\n",
    "        max_len = 0\n",
    "        for c in pre:\n",
    "            max_len = max(max_len, post[c] - pre[c])\n",
    "        return max_len\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefix = 0\n",
    "        dic = defaultdict(list)\n",
    "        dic[0].append(0)\n",
    "        for i in range(0, n):\n",
    "            prefix += 1 if nums[i] == 1 else -1\n",
    "            dic[prefix].append(i + 1)\n",
    "        res = -1\n",
    "        for v in dic.values():\n",
    "            res = max(res, max(v) - min(v))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        count_0 = 0\n",
    "        count_1 = 0\n",
    "\n",
    "        pre = {0: -1}\n",
    "        post = {0: -1}\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                count_0 += 1\n",
    "            else:\n",
    "                count_1 += 1\n",
    "            \n",
    "            count_1_0 = count_1 - count_0\n",
    "\n",
    "            if count_1_0 not in pre:\n",
    "                pre[count_1_0] = i \n",
    "\n",
    "            post[count_1_0] = i \n",
    "\n",
    "        max_len = 0\n",
    "        for c in pre:\n",
    "            max_len = max(max_len, post[c] - pre[c])\n",
    "        return max_len\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        res = 0\n",
    "        mapping = collections.defaultdict(list)\n",
    "        mapping[0] = [-1]\n",
    "        \n",
    "        sum_0 = 0\n",
    "        sum_1 = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 0:\n",
    "                sum_0 += 1\n",
    "            else:\n",
    "                sum_1 += 1\n",
    "            mapping[sum_1 - sum_0].append(i)\n",
    "            if len(mapping[sum_1 - sum_0]) > 1:\n",
    "                res = max(res, mapping[sum_1 - sum_0][-1] - mapping[sum_1 - sum_0][0])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        def change(x):\n",
    "            return x if x==1  else -1\n",
    "        nums = [change(x) for x in nums]\n",
    "        n =  len(nums)\n",
    "        pre =  [nums[0]] * n\n",
    "        dict1,dict2 =  dict(),dict()\n",
    "        dict1[pre[0]],dict2[pre[0]] = 0,0\n",
    "        for  i in range(1,n):\n",
    "            pre[i] = pre[i-1] + nums[i]\n",
    "            dict2[pre[i]] = i\n",
    "        for i in range(n-1,-1,-1):\n",
    "            dict1[pre[i]] = i\n",
    "        \n",
    "        dict1[0]=  -1\n",
    "        ans = 0\n",
    "        for k,v in dict1.items():\n",
    "            if k in dict2:\n",
    "                ans = max(ans,dict2[k]-v)\n",
    "\n",
    "        return ans\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        #1,1,1,0,1,0,1,0,0,1,1,1,0,0,0,\n",
    "        s_dic = {0:[-1]}\n",
    "        cur_num = 0\n",
    "        res = 0\n",
    "        for i,v in enumerate(nums):\n",
    "            if v==1: cur_num+=1\n",
    "            else: cur_num-=1\n",
    "            if cur_num in s_dic: \n",
    "                s_dic[cur_num].append(i)\n",
    "                res = max(res,i-min(s_dic[cur_num]))\n",
    "            else: \n",
    "                s_dic[cur_num] = [i]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0]*n\n",
    "        ans = 0\n",
    "        pre[0] = 1 if nums[0]==1 else -1\n",
    "        for i in range(1, n):\n",
    "            if nums[i]==0:\n",
    "                pre[i] = pre[i-1]-1\n",
    "            else:\n",
    "                pre[i] = pre[i-1]+1\n",
    "        dic = defaultdict(list)\n",
    "        dic[0].append(-1)\n",
    "        for i in range(n):\n",
    "            if pre[i] in dic:\n",
    "                j = min(dic[pre[i]])\n",
    "                ans = max(ans, i-j)\n",
    "            dic[pre[i]].append(i)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i]==0:\n",
    "                nums[i]=-1#把所有的0变为1\n",
    "        q=[0]\n",
    "        for i in range(n):\n",
    "            q.append(q[-1]+nums[i])#计算前缀和\n",
    "        d=defaultdict(list)\n",
    "        for i in range(len(q)):\n",
    "            d[q[i]].append(i)  #统计相同数字的下标\n",
    "        r=0\n",
    "        for k,v in d.items():\n",
    "            if len(v)>1:\n",
    "                r=max(r,v[-1]-v[0]) #计算间隔最大的\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        result = 0\n",
    "        for idx in range(len(nums)):\n",
    "            if nums[idx] == 0:\n",
    "                nums[idx] = -1\n",
    "        dp = [0] * (len(nums) + 1)\n",
    "        d = collections.defaultdict(list)\n",
    "        d[0].append(0)\n",
    "        for idx in range(1, len(dp)):\n",
    "            dp[idx] = dp[idx - 1] + nums[idx - 1]\n",
    "            if dp[idx] in d:\n",
    "                pre = min(d[dp[idx]])\n",
    "                # print(idx, dp[idx], result, dp)\n",
    "                result = max(result, idx - pre)\n",
    "            d[dp[idx]].append(idx)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        count_0 = 0\n",
    "        count_1 = 0\n",
    "\n",
    "        pre = {0: -1}\n",
    "        post = dict()\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                count_0 += 1\n",
    "            else:\n",
    "                count_1 += 1\n",
    "            \n",
    "            if count_1 - count_0 not in pre:\n",
    "                pre[count_1 - count_0] = i \n",
    "\n",
    "            post[count_1 - count_0] = i \n",
    "        \n",
    "        print(pre)\n",
    "        print(post)\n",
    "        max_len = 0\n",
    "        for c in pre:\n",
    "            if c in post:\n",
    "                max_len = max(max_len, post[c] - pre[c])\n",
    "        return max_len\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        presum=[0]\n",
    "        pos=collections.defaultdict(list)\n",
    "        pos[0]=[-1]\n",
    "        ans=0\n",
    "\n",
    "        for i,x in enumerate(nums):\n",
    "            if x==0:\n",
    "                x=-1\n",
    "            s=presum[-1]+x\n",
    "            presum.append(s)\n",
    "            if pos[s]:\n",
    "                ans=max(ans,i-pos[s][0])\n",
    "            pos[s].append(i)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        if 0 not in nums or 1 not in nums:\n",
    "            return 0\n",
    "        if len(nums)==1:\n",
    "            return 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==0:\n",
    "                nums[i]=-1\n",
    "        prefix=[0,nums[0]]\n",
    "        for i in range(1,len(nums)):\n",
    "            prefix.append(prefix[-1]+nums[i])\n",
    "        m=collections.defaultdict(list)\n",
    "        for i,num in enumerate(prefix):\n",
    "            m[num].append(i)\n",
    "        res=0\n",
    "        for i in m.keys():\n",
    "            if len(m[i])==1:\n",
    "                res=max(res,1)\n",
    "            else:\n",
    "                res=max(res,m[i][-1]-m[i][0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        count_0 = 0\n",
    "        count_1 = 0\n",
    "\n",
    "        pre = {0: -1}\n",
    "        post = dict()\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                count_0 += 1\n",
    "            else:\n",
    "                count_1 += 1\n",
    "            \n",
    "            if count_1 - count_0 not in pre:\n",
    "                pre[count_1 - count_0] = i \n",
    "\n",
    "            post[count_1 - count_0] = i \n",
    "\n",
    "        max_len = 0\n",
    "        for c in pre:\n",
    "            if c in post:\n",
    "                max_len = max(max_len, post[c] - pre[c])\n",
    "        return max_len\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        dicts = {}\n",
    "        sum = 0 \n",
    "        for i in range(len(nums)):\n",
    "            num = -1 if nums[i] == 0 else nums[i]\n",
    "            sum += num \n",
    "            if sum in dicts:\n",
    "                dicts[sum] = dicts[sum] + [i]\n",
    "            else:\n",
    "                dicts[sum] = [i]\n",
    "        result = 0 \n",
    "        for k, arr in dicts.items():\n",
    "            if k == 0 and arr[-1] + 1 > result:\n",
    "                result = arr[-1] + 1 \n",
    "            if len(arr) >=2 and arr[-1] - arr[0] > result:\n",
    "                result = arr[-1] - arr[0]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        dicts = {}\n",
    "        sum = 0 \n",
    "        for i in range(len(nums)):\n",
    "            num = -1 if nums[i] == 0 else nums[i]\n",
    "            sum += num \n",
    "            if sum in dicts:\n",
    "                dicts[sum] = dicts[sum] + [i]\n",
    "            else:\n",
    "                dicts[sum] = [i]\n",
    "        result = 0 \n",
    "        for k, arr in dicts.items():\n",
    "            if k == 0 and arr[-1] + 1 > result:\n",
    "                result = arr[-1] + 1 \n",
    "            if len(arr) >=2 and arr[-1] - arr[0] > result:\n",
    "                result = arr[-1] - arr[0]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        data={};  #0比1个数多几个\n",
    "        ret=0;\n",
    "        cur0=0;cur1=0;\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==0:cur0+=1;\n",
    "            else:cur1+=1;\n",
    "            if cur0==cur1:\n",
    "                #print(cur0)\n",
    "                if i+1>ret:ret=i+1;\n",
    "            \n",
    "            #前面某一段 x个0 y个1，当前cur0 个0 cur1个1\n",
    "            key=str(cur0-cur1)\n",
    "            if  key in data:\n",
    "                 lindex=data[key][0];\n",
    "                 if i-lindex>ret:ret=i-lindex;         \n",
    "            \n",
    "            if key in data:data[key].append(i);\n",
    "            else:data[key]=[i];\n",
    "        return ret;\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        p = defaultdict(list)\n",
    "        p[0] = [-1]\n",
    "        cnt = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            cnt += 1 if x else -1\n",
    "            p[cnt].append(i)\n",
    "        # print(cnt)\n",
    "        # print(p)\n",
    "        res = 0 \n",
    "        for k, v in p.items():\n",
    "            res = max(res, v[-1] - v[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        preSum = 0\n",
    "        counter = {0:[-1]} # 和:下标\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            preSum += 1 if nums[i] == 1 else -1\n",
    "\n",
    "            if preSum not in counter:\n",
    "                counter[preSum] = [i]\n",
    "            else:\n",
    "                counter[preSum].append(i)\n",
    "                ans = max(ans, i - counter[preSum][0])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        p = defaultdict(list)\n",
    "        p[0] = [-1]\n",
    "        cnt = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            cnt += 1 if x else -1\n",
    "            p[cnt].append(i)\n",
    "        # print(cnt)\n",
    "        # print(p)\n",
    "        res = 0 \n",
    "        for k, v in p.items():\n",
    "            res = max(res, v[-1] - v[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        group={'0':[-1]}\n",
    "        sums=0\n",
    "        for index,val in enumerate(nums):\n",
    "            if val==0:\n",
    "                val=-1\n",
    "            sums+=val\n",
    "            if str(sums) in group:\n",
    "                group[str(sums)].append(index)\n",
    "            else:\n",
    "                group[str(sums)]=[index]\n",
    "        max_len=[]\n",
    "        for i in group:\n",
    "            if len(group[i])>=2:\n",
    "                max_len.append(group[i][-1]-group[i][0])\n",
    "        if max_len!=[]:\n",
    "            return max(max_len)\n",
    "        else:\n",
    "            return 0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefixSums = [0] * (n + 1)\n",
    "        table = {0 : [0]}\n",
    "        ans = 0\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            prefixSums[i + 1] = prefixSums[i] + (1 if x else -1)\n",
    "            if prefixSums[i + 1] in table:\n",
    "                ans = max(ans, i + 1 - table[prefixSums[i + 1]][0])\n",
    "            if prefixSums[i + 1] not in table:\n",
    "                table[prefixSums[i + 1]] = []\n",
    "            table[prefixSums[i + 1]].append(i + 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        sums = [0]\n",
    "        for num in nums:\n",
    "            sums.append(num + sums[-1])\n",
    "        \n",
    "        n = len(sums)\n",
    "        hash = {}\n",
    "        ans = 0\n",
    "        for i, s in enumerate(sums):\n",
    "            t = 2 * s - i\n",
    "            if t not in hash:\n",
    "                hash[t] = []\n",
    "            if hash[t]:\n",
    "                ans = max(ans, i - hash[t][0])\n",
    "            hash[t].append(i)\n",
    "        return ans\n",
    "\n",
    "# [0, 1, 0, 1 ,1 ,0 ,1 ,0]\n",
    "# [0, 0, 1, 1, 2, 3, 3, 4, 4]\n",
    "\n",
    "\n",
    "#s : 1的个数\n",
    "#i-s: 0的个数\n",
    "#2s - i:  1的个数 - 0的个数\n",
    "#target = 2s - i 多这么多，减去这么多就行了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        sums = []\n",
    "        one = 0\n",
    "        allsum = 0\n",
    "        for i in nums:\n",
    "            one+=i\n",
    "            allsum +=1\n",
    "            sums.append(2*one-allsum)\n",
    "        mpleft = dict()\n",
    "        mpright = dict()\n",
    "        res = 0\n",
    "        for index,i in enumerate(sums):\n",
    "            if mpleft.get(i) is None:\n",
    "                mpleft[i] = index\n",
    "            if i==0:\n",
    "                res = index+1\n",
    "        for index, i in enumerate(sums[::-1]):\n",
    "            if mpright.get(i) is None:\n",
    "                mpright[i] = len(sums)-1-index\n",
    "\n",
    "        for k,v in mpleft.items():\n",
    "            length = mpright[k]-v\n",
    "            res = max(length, res)\n",
    "        return res        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        prefix = [0]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 1:\n",
    "                prefix.append(prefix[i]+1)\n",
    "            else:\n",
    "                prefix.append(prefix[i]-1)\n",
    "        print(prefix)\n",
    "        h_map = {}\n",
    "        for index in range(len(prefix)):\n",
    "            if prefix[index] not in h_map.keys():\n",
    "                h_map[prefix[index]] = []\n",
    "                h_map[prefix[index]].append(index)\n",
    "            else:\n",
    "                h_map[prefix[index]].append(index)\n",
    "        print(h_map)\n",
    "        max_length = 0\n",
    "        for index,arr in h_map.items():\n",
    "            if len(arr) >=2:\n",
    "                max_length = max(max_length,arr[-1]-arr[0])\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        sums = list()\n",
    "        sum_value = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 0:\n",
    "                sum_value += -1\n",
    "            else:\n",
    "                sum_value += 1\n",
    "            sums.append(sum_value)\n",
    "        print(sums)\n",
    "        record = defaultdict(list)\n",
    "        record[0].append(-1)\n",
    "        result = 0\n",
    "        for i in range(len(sums)):\n",
    "            if len(record[sums[i]]) != 0:\n",
    "                if i - record[sums[i]][0] > result:\n",
    "                    result = i - record[sums[i]][0]\n",
    "            if len(record[sums[i]]) == 0:\n",
    "                record[sums[i]].append(i)\n",
    "        return result\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        pre = [0] * (len(nums) + 1)\n",
    "        has = dict()\n",
    "        su = 0\n",
    "        ans = 0\n",
    "        has[0]=[0]\n",
    "        \n",
    "        for i, n in enumerate(nums):\n",
    "            su += n\n",
    "            pre[i+1] = su\n",
    "            if 2*su-i-1 not in has:\n",
    "                has[2*su-i-1] = []\n",
    "            else:\n",
    "                temp = has[2*su-i-1]\n",
    "                margin = i + 1 - min(temp)\n",
    "                if margin > ans: ans = margin\n",
    "            has[2*su-i-1].append(i+1)\n",
    "            # print(has)\n",
    "        return ans\n",
    "        \n",
    "            \n",
    "            \n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        n_0 = 0\n",
    "        n_1 = 0\n",
    "        dict_n = dict()\n",
    "        for idx, i in enumerate(nums):\n",
    "            if i == 0:\n",
    "                n_0 += 1\n",
    "            else :\n",
    "                n_1 += 1\n",
    "            if dict_n.__contains__(n_0-n_1):\n",
    "                dict_n[n_0-n_1].append(idx)\n",
    "            else:\n",
    "                dict_n[n_0-n_1] = [idx]\n",
    "\n",
    "        res = 0\n",
    "        for k in dict_n.keys():\n",
    "            if k == 0:\n",
    "                res = max(res, max(dict_n[k])+1)\n",
    "            else:\n",
    "                if len(dict_n[k]) > 1:\n",
    "                    res = max(res, dict_n[k][-1]-dict_n[k][0])\n",
    "        print(dict_n)\n",
    "        return res\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "        pre_dict = {0: -1,1:1}\n",
    "        nums = [pre_dict[i] for i in nums]\n",
    "\n",
    "        sum_dict = collections.defaultdict(list)\n",
    "        sum_count = 0\n",
    "        sum_dict[0] = [0]\n",
    "        for i in range(len(nums)):\n",
    "            sum_count+=nums[i]\n",
    "            sum_dict[sum_count].append(i+1)\n",
    "\n",
    "        ans = 0\n",
    "        for k in sum_dict.keys():\n",
    "            if len(sum_dict[k])>=2:\n",
    "                ans = max(ans,sum_dict[k][-1]-sum_dict[k][0])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)          \n",
    "\n",
    "        count = [0 for _ in range(n)]\n",
    "        dic = collections.defaultdict(list)\n",
    "        dic[0].append(-1)\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if i > 0:\n",
    "                count[i] = count[i - 1]\n",
    "            \n",
    "            if num == 0:\n",
    "                count[i] -= 1\n",
    "            else:\n",
    "                count[i] += 1\n",
    "            \n",
    "            if len(dic[count[i]]) == 2: \n",
    "                dic[count[i]][1] = i\n",
    "            else:\n",
    "                dic[count[i]].append(i)\n",
    "\n",
    "        max_len = 0\n",
    "        for count, ls in dic.items():\n",
    "            if len(ls) <= 1: continue   \n",
    "\n",
    "            max_len = max(max_len, ls[1] - ls[0])\n",
    "        return max_len\n",
    "            \n",
    "\n",
    "                 \n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
